1. Field of the Invention
This invention generally relates to navigation systems and more specifically to a digital processing method in a receiver and improvements in satellite navigation systems such as the U.S. Global Positioning System (GPS), the Russian Global Navigation Satellite System (GLONASS) and the European Galileo system. For the sake of simplicity, reference will be made below only to the GPS system. The invention is directly applicable to other satellite navigation systems such as GLONASS and Galileo.
2. Description of the Prior Art
A conventional GPS receiver contains an antenna and an analogous front-end (AFE) followed by a digital section having dedicated signal processing circuitry and a digital CPU with related program and data memory and external data interface controllers. The antenna together with the analogous front-end intercept, select (band-pass filter), amplify GPS signals, convert them to a convenient intermediate frequency (IF) normally ranging from DC to several tens of MHz. To perform frequency conversion, the AFE utilizes a reference frequency from a stable reference oscillator. The AFE typically outputs digitized samples of a combination of signals and accompanying noise at IF. The frequency of sampling the AFE output is selected according to the Nyquist criterion, and for the Clear/Acquisition (C/A) GPS signal component is, at least about 2 MHz. A number of bits in digital AFE samples varies from one to three or four bits.
A digital section of the GPS receiver contains several correlator channels that perform correlation processing of several GPS satellite signals in parallel. GPS signals employ phase shift keying modulation with pseudo-random noise codes, see, for example, “Understanding GPS: Principles and Applications. Edited by Elliott D. Kaplan. Artech House, Boston, London, 1996, pp. 83-97”. Received signals are characterized by a priori uncertainty of signal parameters: its code phase due to unknown (or not ideally known) time of the signal coming to the receiver, and its carrier frequency due to unknown (or not ideally known) Doppler shift and the reference oscillator frequency drift. Signal search in a GPS receiver, i.e. resolution of the above-mentioned uncertainty, requires time. Many applications of GPS need receivers that are capable of acquiring signals rapidly in difficult signal environments. For example, this can be reception of weak GPS signals indoors and in urban canyons. A short time to acquire these weak signals is important both from a direct viewpoint of a user requirement to get the first position fix as soon as possible, and from the viewpoint of supply energy reduction as a result of a short time-to-first-fix (TTFF).
The first, and straightforward, way to accelerate GPS signal processing in receivers is to increase the number of parallel correlator channels. It is effective (until some practical limit), and it is quite a common practice in design of modern GPS receivers. Examples are: U.S. Pat. No. 5,901,171 to Kohli et al., or PCT Application No. 2000/65751 by Abraham et al., or almost every GPS receiver on the market. The number of parallel correlator channels reaches 12, 24, and sometimes more. Limits of employing this way of signal processing acceleration in GPS receivers arise due to a proportional growth of hardware complexity and consumed energy with the increase of the number of correlator channels.
Another effective way to accelerate signal processing in GPS receivers is to process signals at a faster-than-real-time rate. The fundamental patents claiming this method are: U.S. Pat. No. 5,420,593 to Niles, and U.S. Pat. No. 5,329,549 to Kawasaki. The essence of the method, according to both patents, is that digitized samples of a combination of signal and noise are written into a digital memory at a real-time rate, and then these samples are reproduced from the memory and processed in correlator channels at a significantly higher rate. As a result, a significantly larger amount of candidate signal replicas are tried in a unit of time thus accelerating the overall signal search process. Different receiver options implementing the method can be found, for example, in U.S. Pat. No. 5,901,171 to Kohli et al., U.S. Pat. No. 6,091,785 to Lennen, U.S. Pat. No. 6,044,105 to Gronemeyer, U.S. Pat. No. 6,118,808 to Tiemann, and U.S. Pat. No. 6,300,899 to King. The effect gained with the method is bound by the allowed rate of digital processing that reflects the existing technical level in microelectronics, and/or the acceptable power consumed by the digital processing hardware that is, normally, directly proportional to the processing rate.
The third way to accelerate signal processing in GPS receivers is to implement parallel (pseudo-parallel) spectral analysis of preliminary correlation processing results with the help of a Fast Fourier Transform (FFT) or a Discrete Fourier Transform (DFT) method.
Examples of the use of FFT for acquisition of GPS signals may be found in U.S. Pat. No. 4,701,934 to Jasper, and PCT Application No. 2001/86318 by Bryant et al., or U.S. Pat. Application No. 2002/0005802 by Bryant.
Examples of the use of DFT for acquisition of GPS signals may be found in U.S. Pat. No. 5,347,284 to Volpi et al., U.S. Pat. No. 5,535,237 to Volpi et al., PCT Application No. 2002/23327 by Van Wechel, PCT Application No. 2002/23783 by van Wechel, and U.S. Pat. No. 6,327,473 to Soliman et al.
The above-described third way to accelerate signal processing in GPS receivers also has its bounds of effective use. First, complexity of hardware implementing DFT or FFT grows with the increase of the number of frequency bins analyzed in parallel. Second, not every application of a GPS receiver requires an increase of frequency search bins.